1. Field of the Invention
The field of the invention relates to data processing and in particular to the conversion of virtual addresses produced by a processor to corresponding physical addresses in order to access data stored in a physical address.
2. Description of the Prior Art
It is known in data processing systems for processors to refer to storage locations using virtual addresses, while the data itself is stored in a location identified by a physical address. When accessing this data any virtual address produced by the processor will need to be converted to a physical address. This can slow the procedure, as the data cannot be accessed until it is converted to a physical address.
A known way of converting a virtual address to a physical address is by the use of a translation lookaside buffer (TLB). The TLB receives a virtual address from a processor and converts it to a physical address. The TLB is quick and easy to access and therefore performs the conversion relatively quickly. However, the TLB does not store a complete mapping of virtual to physical addresses only storing a subset, this subset generally being mappings that have been used recently. Thus, it may be that a data access requests a virtual address that is not stored in the TLB. In such a case the data processor will need to retrieve this information, usually from a table in main memory. Compared to the TLB access this is a relatively lengthy and power costly operation. The TLB will then be updated with this recently accessed information. To do this an entry to be overwritten will need to be selected.
The TLB may be arranged in a number of ways. In a fully associative TLB all entries in the TLB are available for selection, while in a set associative TLB there is a smaller selection of possible storage locations for an entry. In systems of the prior art the selection of which entry to overwrite has conventionally been made either randomly, or in a “round robin” way such that the oldest entry is selected, or in a way such that the least recently accessed entry is selected. The choice has an impact on performance as a miss in the TLB will require a memory access and extra time and power to be consumed, thus, overwriting an entry that would later have been used will damage performance.
It would be desirable to be able to consistently select entries that are unlikely to be used again soon.